//给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符
//串。如果答案不存在，则返回空字符串。 
//
// 示例 1: 
//
// 
//输入:
//s = "abpcplea", d = ["ale","apple","monkey","plea"]
//
//输出: 
//"apple"
// 
//
// 示例 2: 
//
// 
//输入:
//s = "abpcplea", d = ["a","b","c"]
//
//输出: 
//"a"
// 
//
// 说明: 
//
// 
// 所有输入的字符串只包含小写字母。 
// 字典的大小不会超过 1000。 
// 所有输入的字符串长度不会超过 1000。 
// 
// Related Topics 排序 双指针 
// 👍 122 👎 0

package com.leetcode.editor.cn;

import java.util.List;

//Java：通过删除字母匹配到字典里最长单词
class P524LongestWordInDictionaryThroughDeleting {
    public static void main(String[] args) {
        Solution solution = new P524LongestWordInDictionaryThroughDeleting().new Solution();
        // TO TEST
        String s = "abpcplea";
        List<String> d = List.of("ale", "apple", "monkey", "plea");
        System.out.println(solution.findLongestWord(s, d));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String findLongestWord(String s, List<String> d) {
            String ans = "";
            for (String s1 : d) {
                if (check(s, s1) && (s1.length() > ans.length() || (s1.length() == ans.length() && s1.compareTo(ans) < 0))) {
                    ans = s1;
                }
            }
            return ans;
        }

        public boolean check(String s, String s1) {
            char[] chars = s.toCharArray();
            char[] charsS1 = s1.toCharArray();
            int index = 0;
            int index1 = 0;
            while (index < chars.length && index1 < charsS1.length) {
                if (chars[index] == charsS1[index1]) {
                    index++;
                    index1++;
                } else {
                    index++;
                }
            }
            return index1 == charsS1.length;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}